package com.wfm.leetcode.editor.cn;

/**
 * 移除元素
 * 2025-02-20 17:39:04
 * 左指针指向下一个要赋值的位置，右指针指向要处理的元素
 * 如果右指针元素不等于val，将右指针指向的元素复制到左指针
 * 如果右指针元素等于val，此时左指针不动，右指针右移一位
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */
class RemoveElement {

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }

    // 优化双指针，解决 1 2 3 4 5 val=1 时，每个元素都要左移的问题
    // 把之前的右指针从右边往左边移动
    // 时间复杂度 O(n)
    // 空间复杂度 O(1)
    public int removeElement2(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            // 如果左边元素=val 把右边的复制过来，如果还相等没关系，还会判断
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new RemoveElement().new Solution();
        
    }
}